#include <bits/stdc++.h>

using namespace std;

class Solution {
public:
    int minChanges(vector<int> &nums, int k) {
        vector<unordered_map<int, int>> hash(k);
        vector<int> size(k);
        int N = nums.size();
        for (int i = 0; i < N; ++i) {
            int group = i % k;
            ++size[group];
            ++hash[group][nums[i]];
        }
        vector<vector<int>> dp(k, vector<int>(1024));
        for (int j = 0; j < 1024; ++j)
            dp[0][j] = size[0] - hash[0][j];
        for (int i = 1; i < k; ++i) {
            int upper = *min_element(dp[i - 1].begin(), dp[i - 1].end()) + size[i];
            fill(dp[i].begin(), dp[i].end(), upper);
            for (auto[x, count] :hash[i]) {
                for (int j = 0; j < 1024; ++j) {
                    dp[i][j ^ x] = min(dp[i][j ^ x], dp[i - 1][j] + size[i] - count);
                }
            }
        }
        return dp[k - 1][0];
    }
};

int main() {
    Solution solution;
    vector<int> nums = {3, 4, 5, 2, 1, 7, 3, 4, 7};
    int k = 3;
    solution.minChanges(nums, k);
}
